package com.xw.class12;

import com.xw.util.GenerateBinaryTreeUtils;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author XW
 * @data 2023/8/3 10:48
 * @description返回二叉树的最大宽度
 */
public class Code02_MaxSizeBinaryTree {

    public static int getMaxSize(GenerateBinaryTreeUtils.Node root){
        if(null == root){
            return 0;
        }
        int times=0;
        int max = 0;
        Queue<GenerateBinaryTreeUtils.Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            if(times == 0){
                times=queue.size();
                max = Math.max(max, queue.size());
            }
            GenerateBinaryTreeUtils.Node cur = queue.poll();
            times--;
            if(null != cur.left){
                queue.add(cur.left);
            }
            if(null != cur.right){
                queue.add(cur.right);
            }
        }
        return max;
    }



    public static int largestBSTSubtree(GenerateBinaryTreeUtils.Node head) {
        if (head == null) {
            return 0;
        }
        return process(head).maxBSTSubtreeSize;
    }

    public static class Info {
        public int maxBSTSubtreeSize;
        public int allSize;
        public int max;
        public int min;

        public Info(int m, int a, int ma, int mi) {
            maxBSTSubtreeSize = m;
            allSize = a;
            max = ma;
            min = mi;
        }
    }

    public static Info process(GenerateBinaryTreeUtils.Node x) {
        if (x == null) {
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int max = x.value;
        int min = x.value;
        int allSize = 1;
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
            allSize += leftInfo.allSize;
        }
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
            allSize += rightInfo.allSize;
        }
        int p1 = -1;
        if (leftInfo != null) {
            p1 = leftInfo.maxBSTSubtreeSize;
        }
        int p2 = -1;
        if (rightInfo != null) {
            p2 = rightInfo.maxBSTSubtreeSize;
        }
        int p3 = -1;
        boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubtreeSize == leftInfo.allSize);
        boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubtreeSize == rightInfo.allSize);
        if (leftBST && rightBST) {
            boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.value);
            boolean rightMinMoreX = rightInfo == null ? true : (x.value < rightInfo.min);
            if (leftMaxLessX && rightMinMoreX) {
                int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
                int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
                p3 = leftSize + rightSize + 1;
            }
        }
        return new Info(Math.max(p1, Math.max(p2, p3)), allSize, max, min);
    }

    // 为了验证
    // 对数器方法
    public static int right(GenerateBinaryTreeUtils.Node head) {
        if (head == null) {
            return 0;
        }
        int h = getBSTSize(head);
        if (h != 0) {
            return h;
        }
        return Math.max(right(head.left), right(head.right));
    }

    // 为了验证
    // 对数器方法
    public static int getBSTSize(GenerateBinaryTreeUtils.Node head) {
        if (head == null) {
            return 0;
        }
        ArrayList<GenerateBinaryTreeUtils.Node> arr = new ArrayList<>();
        in(head, arr);
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i).value <= arr.get(i - 1).value) {
                return 0;
            }
        }
        return arr.size();
    }

    // 为了验证
    // 对数器方法
    public static void in(GenerateBinaryTreeUtils.Node head, ArrayList<GenerateBinaryTreeUtils.Node> arr) {
        if (head == null) {
            return;
        }
        in(head.left, arr);
        arr.add(head);
        in(head.right, arr);
    }

    // 为了验证
    // 对数器方法
    public static GenerateBinaryTreeUtils.Node generateRandomBST(int maxLevel, int maxvalueue) {
        return generate(1, maxLevel, maxvalueue);
    }

    // 为了验证
    // 对数器方法
    public static GenerateBinaryTreeUtils.Node generate(int level, int maxLevel, int maxvalueue) {
        if (level > maxLevel || Math.random() < 0.5) {
            return null;
        }
        GenerateBinaryTreeUtils.Node head = new GenerateBinaryTreeUtils.Node((int) (Math.random() * maxvalueue));
        head.left = generate(level + 1, maxLevel, maxvalueue);
        head.right = generate(level + 1, maxLevel, maxvalueue);
        return head;
    }

    // 为了验证
    // 对数器方法
    public static void main(String[] args) {
        int maxLevel = 4;
        int maxvalueue = 100;
        int testTimes = 100;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            GenerateBinaryTreeUtils.Node head = generateRandomBST(maxLevel, maxvalueue);
            if (largestBSTSubtree(head) != right(head)) {
                System.out.println("出错了！");
            }
            if (getMaxSize(head) != right(head)) {
                level(head);
                System.out.println(" ");
                Queue<String> queue = preSerializeTree(head);
                while (queue.size()!= 0){
                    System.out.print(queue.poll() +" ");
                }
                System.out.println(" ");
                System.out.println("我出错了！" + getMaxSize(head) + "---" + right(head));
            }
        }
        System.out.println("测试结束");
    }

    public static Queue<String> preSerializeTree(GenerateBinaryTreeUtils.Node head){
        Queue<String> queue = new LinkedList<>();
        preOrder(head,queue);
        return queue;
    }

    private static void preOrder(GenerateBinaryTreeUtils.Node head, Queue<String> queue) {
        if(head == null){
            queue.add(null);
        }else{
            queue.add(String.valueOf(head.value));
            preOrder(head.left,queue);
            preOrder(head.right,queue);
        }
    }

    public static void level(GenerateBinaryTreeUtils.Node head){
        if (null == head){
            return;
        }
        Queue<GenerateBinaryTreeUtils.Node> queue = new LinkedList<>();
        queue.add(head);
        while(!queue.isEmpty()){
            GenerateBinaryTreeUtils.Node cur = queue.poll();
            System.out.print(cur.value + " ");

            if(cur.left != null){
                queue.add(cur.left);
            }
            if(cur.right != null){
                queue.add(cur.right);
            }
        }
    }
    

}
